<?xml version="1.0" encoding="ISO-8859-1"?>
<metadatalist>
	<metadata ReferenceType="Conference Proceedings">
		<site>sibgrapi.sid.inpe.br 802</site>
		<holdercode>{ibi 8JMKD3MGPEW34M/46T9EHH}</holdercode>
		<identifier>6qtX3pFwXQZG2LgkFdY/UNhNr</identifier>
		<repository>sid.inpe.br/sibgrapi@80/2008/07.18.15.09</repository>
		<lastupdate>2008:07.18.15.09.32 sid.inpe.br/banon/2001/03.30.15.38 administrator</lastupdate>
		<metadatarepository>sid.inpe.br/sibgrapi@80/2008/07.18.15.09.34</metadatarepository>
		<metadatalastupdate>2022:06.14.00.13.46 sid.inpe.br/banon/2001/03.30.15.38 administrator {D 2008}</metadatalastupdate>
		<doi>10.1109/SIBGRAPI.2008.24</doi>
		<citationkey>AryaFonsMoun:2008:TrApRa</citationkey>
		<title>Tradeoffs in approximate range searching made simpler</title>
		<format>Printed, On-line.</format>
		<year>2008</year>
		<numberoffiles>1</numberoffiles>
		<size>207 KiB</size>
		<author>Arya, Sunil,</author>
		<author>Fonseca, Guilherme D. da,</author>
		<author>Mount, David M.,</author>
		<affiliation>The Hong Kong University of Science and Technology</affiliation>
		<affiliation>University of Maryland</affiliation>
		<affiliation>University of Maryland</affiliation>
		<editor>Jung, Cláudio Rosito,</editor>
		<editor>Walter, Marcelo,</editor>
		<conferencename>Brazilian Symposium on Computer Graphics and Image Processing, 21 (SIBGRAPI)</conferencename>
		<conferencelocation>Campo Grande, MS, Brazil</conferencelocation>
		<date>12-15 Oct. 2008</date>
		<publisher>IEEE Computer Society</publisher>
		<publisheraddress>Los Alamitos</publisheraddress>
		<booktitle>Proceedings</booktitle>
		<tertiarytype>Full Paper</tertiarytype>
		<transferableflag>1</transferableflag>
		<versiontype>finaldraft</versiontype>
		<keywords>range searching, geometric approximation, geometric data structures, computational geometry.</keywords>
		<abstract>Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps > 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range's boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.</abstract>
		<language>en</language>
		<targetfile>tradeoffs-final.pdf</targetfile>
		<usergroup>fonseca@cos.ufrj.br administrator</usergroup>
		<visibility>shown</visibility>
		<mirrorrepository>sid.inpe.br/banon/2001/03.30.15.38.24</mirrorrepository>
		<nexthigherunit>8JMKD3MGPEW34M/46SG4TH</nexthigherunit>
		<nexthigherunit>8JMKD3MGPEW34M/4742MCS</nexthigherunit>
		<citingitemlist>sid.inpe.br/sibgrapi/2022/05.14.04.55 4</citingitemlist>
		<hostcollection>sid.inpe.br/banon/2001/03.30.15.38</hostcollection>
		<lasthostcollection>sid.inpe.br/banon/2001/03.30.15.38</lasthostcollection>
		<url>http://sibgrapi.sid.inpe.br/rep-/sid.inpe.br/sibgrapi@80/2008/07.18.15.09</url>
	</metadata>
</metadatalist>